class bitset():
    """
    bitset:
        perform the bit operation.
    """
    __slots__ = ("__N","__value")
    def __init__(self,N:int,value:int=0x0):# {{{
        """
        N     : The width of bitset
        value : The initial value of bitset, default value is 0x0
        """
        self.__typecheck(N,int)
        self.__typecheck(value,int)
        self.__N = N
        self.__value = [bool()] * N
        if(value != 0):
            for i in range(N):
                self.__value[i] = bool((value >> i) & 0x1)
# }}}

    def __getitem__(self,index):# {{{
        if(isinstance(index,int)):
            self.__rangecheck(index,0,self.__N-1)
            return int(self.__value[index])
        elif(isinstance(index,slice)):
            self.__typecheck(index.start,int)
            self.__typecheck(index.stop,int)
            self.__rangecheck(index.start,index.stop+1,self.__N-1)
            self.__rangecheck(index.stop,0,index.start-1)
            value = 0
            for i in range(index.start - index.stop + 1):
                value += 2**i * self.__value[index.stop+i]
            return value
# }}}

    def __setitem__(self,index,value):# {{{
        self.__typecheck(index,int)
        self.__typecheck(value,int)
        self.__rangecheck(index,0,self.__N-1)
        self.__rangecheck(value,0,1)

        self.__value[index] = value
# }}}

    def __xor__(self,other):# {{{
        """
        return self ^ other(bitset).
        """
        self.__typecheck(other,bitset)
        width = max(self.__N,other.__N)
        temp = bitset(width)
        for i in range(width):
            if(i>=self.__N):
                temp[i] = 0 ^ other.__value[i]
            elif(i>=other.__N):
                temp[i] = self.__value[i] ^ 0
            else:
                temp[i] = self.__value[i] ^ other.__value[i]
        return temp
    # }}}

    def __or__(self,other):# {{{
        temp = bitset(self.__N)
        for i in range(self.__N):
            temp[i] = self.__value[i] | other.__value[i]
        return temp
# }}}

    def __and__(self,other): # {{{
        temp = bitset(self.__N)
        for i in range(self.__N):
            temp[i] = self.__value[i] & other.__value[i]
        return temp 
#}}}

    def __eq__(self,other):#{{{#
        for i in range(self.__N):
            if(self.__value[i] != other.__value[i]):
                return False
        return True
#}}}

    def __ne__(self,other):#{{{#
        for i in range(self.__N):
            if(self.__value[i] != other.__value[i]):
                return True
        return False
#}}}

    def __rshift__(self,index):# {{{
        """
        return self >> index.
        """
        temp = bitset(self.__N)
        for i in range(self.__N-index):
            temp[i] = self.__value[i+index]
        for i in range(index):
            temp[self.__N-index+i] = bool(0)
        return temp
# }}}

    def __lshift__(self,index):# {{{
        """
        return self << index.
        """
        temp = bitset(self.__N)
        for i in range(self.__N-index):
            temp[i+index] = self.__value[i]
        for i in range(index):
            temp[i] = bool(0)
        return temp
# }}}

    def __invert__(self):
        temp = bitset(self.__N)
        for i in range(self.__N):
            temp[i] = not self.__value[i]
        return temp

    def size(self):# {{{
        """
        return the width of bitset.
        """
        return self.__N
# }}}

    def get_value(self):# {{{
        """
        return the value(int) of bitset.
        """
        value = 0
        for i in range(self.__N):
            value += 2**i * self.__value[i]
        return value
# }}}

    def count(self): #{{{
        """
        return the number of 1.
        """
        num = 0
        for i in range(self.__N):
            if(self.__value[i]):
                num += 1
        return num
#}}}

    def any(self):
        """
        if have 1 in bitset return Ture,otherwise return False.
        """
        for i in range(self.__N):
            if(self.__value[i] == True):
                return True
        return False

    def all(self):
        """
        when any bits is 1 return Ture,otherwise return False.
        """
        for i in range(self.__N):
            if(self.__value[i] == False):
                return False
        return Ture

    def __typecheck(self,tp,tps):# {{{
        if(not isinstance(tp,tps)):
            raise TypeError("type error.")
# }}}

    def __rangecheck(self,value,minv=-2**32,maxv=2**32):# {{{
        if(value > maxv or value < minv):
            raise ValueError("The Value range error.")
    # }}}

    def __str__(self):# {{{
        a = ""
        for i in range(self.__N):
            a += str(int(self.__value[self.__N-1-i]))
        return a
# }}}
